package 算法基础模板.chapter_03;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一个n个点m条边的 有向图 ，图中可能存在重边和自环，所有边权均为正值。
 * <p>
 * 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
 * <p>
 * 输入格式
 * 第一行包含整数n和m。
 * <p>
 * 接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
 * <p>
 * 输出格式
 * 输出一个整数，表示1号点到n号点的最短距离。
 * <p>
 * 如果路径不存在，则输出-1。
 * <p>
 * 数据范围
 * 1≤n≤500,
 * 1≤m≤10^5,
 * 图中涉及边长均不超过10000。
 * <p>
 * 输入样例：
 * 3 3
 * 1 2 2
 * 2 3 1
 * 1 3 4
 * 输出样例：
 * 3
 *
 * @author Summerday
 */
public class Dijkstra1 {

    //从这里看，边是比较多的，所有可以用邻接矩阵存数据

    static int N = 510;
    static int m, n;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];

    //注意：有向图和无向图相比，无向图可以看出有向图
    //如果有重边，保留距离最短的那条边
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++) Arrays.fill(g[i], 0x3f3f); //权值不超过10000
        while (m-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            g[a][b] = Math.min(g[a][b], c);// 重边, 保留最短的边
        }

        // 表示1号点到n号点的最短距离
        System.out.println(dijkstra());
    }

    static int dijkstra () {
        Arrays.fill(dist, 0x3f3f);

        dist[1] = 0;// 设置自己的距离为0

        // 迭代n次,一定能找到最后的结果
        for (int i = 0; i < n; i++) {
            int t = -1;// 还没有最短的点
            // 找到未访问过 且距离最短的点(可以用堆优化,找到最小一个数 o(1), 修改的话mlogN)
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
            }

            st[t] = true; // 标记走过了
            // 更新一下dist
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }

        if (dist[n] == 0x3f3f) return -1;
        return dist[n];
    }

}
